package com.ky.leetcode.剑指Offer;

/*

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

    示例 1：
    输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
    输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

    示例 2：
    输入：head = [[1,1],[2,1]]
    输出：[[1,1],[2,1]]

    示例 3：
    输入：head = [[3,null],[3,0],[3,null]]
    输出：[[3,null],[3,0],[3,null]]

    示例 4：
    输入：head = []
    输出：[]
    解释：给定的链表为空（空指针），因此返回 null。

*/

import java.util.HashMap;
import java.util.Map;

public class 剑指Offer35复杂链表的复制 {
    public static void main(String[] args) {
        Node head = new Node(3);
        Node headNext = new Node(3);
        Node last = new Node(3);
        head.next = headNext;
        headNext.next = last;
        head.random = null;
        headNext.random = head;
        head.random = null;
        Solution solution = new Solution();
        solution.copyRandomList(head);
    }

    static class Solution {
        public Node copyRandomList(Node head) {
            Node last = null;
            Node newHead = head;
            Map<Integer, Node> map = new HashMap<>();
            int index = 0;
            while (newHead != null) {
                if (last == null) {
                    last = new Node(newHead.val);
                } else {
                    Node oldLast = last;
                    last = new Node(newHead.val);
                    oldLast.next = last;
                }
                map.put(index, newHead);
                newHead = newHead.next;
                index++;
            }
            newHead = head;
            while (newHead != null) {
                if (last == null) {
                    last = new Node(newHead.val);
                } else {
                    Node oldLast = last;
                    last = new Node(newHead.val);
                    oldLast.next = last;
                }
                map.put(index, newHead);
                newHead = newHead.next;
                index++;
            }
            return last;
        }
    }

    public static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

}
